package com.leetcode2;

import java.util.LinkedList;
import java.util.List;

public class Index797allPathsSourceTarget {
	
	List<List<Integer>> res;
	public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
		LinkedList<Integer> path = new LinkedList<>();
		dfs(graph,0,path);
		return res;
    }
	
	public void dfs(int[][] graph,int v,LinkedList<Integer> path) {
		path.addLast(v);
		if(v == graph.length - 1) {
			res.add(new LinkedList<Integer>(path));
			path.removeLast();
			return;
		}
		
		for(int t : graph[v])
			dfs(graph,t,path);
		
		path.removeLast();
	}
}
